public class RBTree {
    static class RBTreeNode{
        int val;
        RBTreeNode left;
        RBTreeNode right;
        RBTreeNode parent;
        COLOR color = COLOR.RED;
        public RBTreeNode(int val) {
            this.val = val;
        }
    }
    RBTreeNode root;

    public boolean insert(int val){
        RBTreeNode node = new RBTreeNode(val);
        if(root==null){
            root=node;
            node.color=COLOR.BLACK;
            return true;
        }
        RBTreeNode cur = root;
        RBTreeNode parent=null;
        while(cur!=null){
            if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val==val){
                return false;
            }else if(cur.val>val){
                parent=cur;
                cur=cur.left;
            }
        }
        if(parent.val>val){
            parent.left=node;
        }else{
            parent.right=node;
        }

        node.parent=parent;
        cur=node;

        while(parent!=null&&parent.color==COLOR.RED){
            RBTreeNode grandFather=parent.parent;
            if(parent==grandFather.left){
                RBTreeNode uncle=grandFather.right;
                if(uncle!=null&&uncle.color==COLOR.RED){
                    parent.color=COLOR.BLACK;
                    uncle.color=COLOR.BLACK;
                    grandFather.color=COLOR.RED;

                    cur=grandFather;
                    parent=cur.parent;
                }else{

                    //请况三:
                    if(cur==parent.right){
                        rotateLeft(parent);
                        RBTreeNode tmp=cur;
                        cur=parent;
                        parent=tmp;
                    }//继续进行右旋

                    //情况二：
                    //且cur==parent.left:
                    //uncle不存在或为黑
                    rotateRight(grandFather);
                    parent.color=COLOR.BLACK;
                    grandFather.color=COLOR.RED;
                }
            }else{
                //parent==grandFather.right
                RBTreeNode uncle=grandFather.left;
                if (uncle!=null&&uncle.color==COLOR.RED){
                    parent.color=COLOR.BLACK;
                    uncle.color=COLOR.BLACK;
                    grandFather.color=COLOR.RED;

                    cur=grandFather;
                    parent=cur.parent;
                }else{
                    //uncle为空或为黑
                    //情况三：cur==parent.left
                    if(cur==parent.left){
                        rotateRight(parent);
                        RBTreeNode tmp=cur;
                        cur=parent;
                        parent=tmp;
                    }

                    //情况二：cur==parent.right
                    rotateLeft(grandFather);
                    grandFather.color=COLOR.RED;
                    parent.color=COLOR.BLACK;
                }
            }
            root.color=COLOR.BLACK;
        }
        return true;
    }
    private void rotateRight(RBTreeNode parent){
        RBTreeNode subL=parent.left;
        RBTreeNode subLR=subL.right;

        parent.left=subLR;
        subL.right=parent;

        RBTreeNode parentP=parent.parent;
        if(subLR!=null){
            subLR.parent=parent;
        }
        if(parent==root){
            root=subL;
            subL.parent=null;
        }else{
            if (parentP.left==parent){
                parentP.left=subL;
            } else {
                parentP.right=subL;
            }
            subL.parent=parentP;
        }
        parent.parent=subL;
    }
    private void rotateLeft(RBTreeNode parent){
        RBTreeNode subR=parent.right;
        RBTreeNode subRL=subR.left;

        parent.right=subRL;
        subR.left=parent;
        if (subRL!=null){
            subRL.parent=parent;
        }
        RBTreeNode parentP=parent.parent;
        subR.parent=parentP;
        if(parent==root){
            root=subR;
            root.parent=null;
        }else if(parentP.left==parent){
            parentP.left=subR;
        } else {
            parentP.right=subR;
        }
        parent.parent=subR;
    }
    //中序遍历
    public void inorder(RBTreeNode root){
        if (root==null) return ;
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    public boolean isRBTree(RBTreeNode root){
        if(root==null) return true;
        if (root.color!=COLOR.BLACK){
            System.out.println("违反了性质2：根节点是红色");
            return false;
        }
        int countBlack=0;
        RBTreeNode cur=root;
        while(cur!=null){
            if(cur.color==COLOR.BLACK){
                countBlack++;
            }
            cur=cur.left;
        }
        return checkBlackNum(root,0,countBlack);
    }
    private boolean checkBlackNum(RBTreeNode root,int pathBlackNum,int countBlackNum){
        if(root==null){
            if (pathBlackNum==countBlackNum){
                return true;
            }else{
                System.out.println("违反了性质4：路径的黑色节点个数不一致");
                return false;
            }
        }
        if(root.color==COLOR.RED&&root.parent.color==COLOR.RED){
            System.out.println("违反性质3：不能有连续的2个红色节点");
            return false;
        }
        if(root.color==COLOR.BLACK){
            pathBlackNum++;
        }
        return checkBlackNum(root.left,pathBlackNum,countBlackNum)
                &&checkBlackNum(root.right,pathBlackNum,countBlackNum);
    }
}
